package BinaryTree;

public class BinaryTree<T> implements BinaryTTree<T> {

	public Node<T> root; // 根结点，结点结构为二叉链表

	/**
	 * 构造空二叉树
	 */
	public BinaryTree() {
		this.root = null;
	}

	/**
	 * 以先序序列构造二叉树
	 * 
	 * @param prelist
	 *            先序序列
	 */
	public BinaryTree(T[] prelist) {
		this.root = create(prelist);
	}

	public BinaryTree(BinaryTree<T> bitree) {
		this.root = copy(bitree.root);
	}

	/**
	 * 以先序和中序列构造二叉树
	 * 
	 * @param prelist
	 *            先序序列
	 * @param inlist
	 *            中序序列
	 */
	public BinaryTree(T[] prelist, T[] inlist) {
		this.root = create(prelist, inlist, 0, 0, prelist.length);
	}

	// 以先根和中根序列创建一棵子树，子树根结点值是prelist[preStart]，n指定子序列长度，
	// 返回所创建子树的根结点
	private Node<T> create(T[] prelist, T[] inlist, int preStart, int inStart, int n) {
		if (n <= 0)
			return null;
		T elem = prelist[preStart]; // 根结点值
		Node<T> p = new Node<T>(elem); // 创建叶子结点
		int i = 0;
		while (i < n && !elem.equals(inlist[inStart + i])) // 在中根序列中查找根值所在位置
			i++;
		p.left = create(prelist, inlist, preStart + 1, inStart, i); // 创建左子树
		p.right = create(prelist, inlist, preStart + i + 1, inStart + i + 1, n - 1 - i); // 创建右子树
		return p;
	}

	/**
	 * 判断二叉树是否空
	 */
	public boolean isEmpty() {
		return this.root == null;
	}

	/**
	 * 先序遍历
	 */
	public void preOrder() {
		System.out.print("先序遍历二叉树：  ");
		preOrder(root); // 调用先根次序遍历二叉树的递归方法
		System.out.println();
	}

	/**
	 * 先序遍历
	 */
	private void preOrder(Node<T> root) {
		if (root != null) // 若二叉树不空
		{
			System.out.print(root.data.toString() + " "); // 访问当前结点
			preOrder(root.left); // 按先根次序遍历当前结点的左子树，递归调用
			preOrder(root.right); // 按先根次序遍历当前结点的右子树，递归调用
		}
	}

	public String toString() {
		return toString(root);
	}

	private String toString(Node<T> p) {
		if (p == null)
			return "";
		return p.data.toString() + " " + toString(p.left) + toString(p.right);// 递归调用
	}

	/**
	 * 中序遍历
	 */
	public void inOrder() {
		System.out.print("中序遍历二叉树：  ");
		inOrder(root);
		System.out.println();
	}

	private void inOrder(Node<T> root) {
		if (root != null) {
			inOrder(root.left); // 中根次序遍历左子树，递归调用
			System.out.print(root.data.toString() + " ");
			inOrder(root.right); // 中根次序遍历右子树，递归调用
		}
	}

	/**
	 * 后序遍历
	 */
	public void postOrder() {
		System.out.print("后序遍历二叉树：  ");
		postOrder(root);
		System.out.println();
	}

	private void postOrder(Node<T> root) {
		if (root != null) {
			postOrder(root.left);
			postOrder(root.right);
			System.out.print(root.data.toString() + " ");
		}
	}

	/**
	 * 返回二叉树的结点个数
	 */
	public int count() {
		return count(root);
	}

	/**
	 * 子树的结点个数
	 * 
	 */
	private int count(Node<T> root) {
		if (root == null)
			return 0;
		return 1 + count(root.left) + count(root.right);
	}

	/**
	 * 返回二叉树的高度
	 */
	public int height() {
		return height(root);
	}

	/**
	 * 返回以p结点为根的子树高度，后根次序遍历
	 */
	private int height(Node<T> root) {
		if (root == null)
			return 0;
		int lh = height(root.left); // 返回左子树的高度
		int rh = height(root.right); // 返回右子树的高度
		return (lh >= rh) ? lh + 1 : rh + 1; // 当前子树高度为较高子树的高度加1
	}

	public T search(T key) // 查找并返回首次出现的关键字为key元素
	{
		return searchNode(root, key).data;
	}

	@SuppressWarnings("unused")
	private Node<T> searchNode(T key) // 查找并返回首次出现的关键字为key元素结点
	{
		return searchNode(root, key);
	}

	// 在以p为根的子树中查找并返回首次出现的关键字为key元素结点，若未找到返回null，先根次序遍历
	private Node<T> searchNode(Node<T> p, T key) {
		if (p == null || key == null)
			return null;
		if (p.data.equals(key))
			return p; // 查找成功，返回找到结点
		Node<T> find = searchNode(p.left, key); // 在左子树中查找，递归调用
		if (find == null) // 若在左子树中未找到
			find = searchNode(p.right, key); // 则继续在右子树中查找，递归调用
		return find; // 返回查找结果
	}

	// 返回node结点的父母结点，若空树、未找到或node为根，则返回nsull
	public Node<T> getParent(Node<T> node) {
		if (root == null || node == null || node == root)
			return null;
		return getParent(root, node);
	}

	// 在以p为根的子树中查找并返回node结点的父母结点
	private Node<T> getParent(Node<T> p, Node<T> node) {
		if (p == null)
			return null;
		if (p.left == node || p.right == node)
			return p;
		Node<T> find = getParent(p.left, node);
		if (find == null)
			find = getParent(p.right, node);
		return find;
	}

	// 以标明空子树的先根序列构造一棵子二叉树，子树的根值是prelist[i]，返回所创建子树的根结点
	private int i = 0;

	private Node<T> create(T[] prelist) {
		Node<T> p = null;
		if (i < prelist.length) {
			T elem = prelist[i];
			i++;
			if (elem != null) // 不能elem!="^"，因为T不一定是String
			{
				p = new Node<T>(elem); // 创建叶子结点
				p.left = create(prelist); // 创建p的左子树
				p.right = create(prelist); // 创建p的右子树
			}
		}
		return p;
	}

	/**
	 * 插入元素x作为根结点，原根结点作为其左孩子
	 */
	public void insertRoot(T x) {
		this.root = new Node<T>(x, this.root, null);
	}

	// 插入元素x作为p结点的孩子，若leftChild为true，插入结点作为左孩子，否则作为右孩子
	// 返回插入结点。若p==null，将抛出空对象异常
	public Node<T> insertChild(Node<T> p, T x, boolean leftChild) {
		if (x == null)
			return null;
		if (leftChild) {
			p.left = new Node<T>(x, p.left, null); // 插入x结点作为p的左孩子，p原左孩子成为x的左孩子
			return p.left; // 返回插入结点
		}
		p.right = new Node<T>(x, null, p.right); // 插入x结点作为p的右孩子，p原右孩子成为x的右孩子
		return p.right;
	}

	// 删除p结点的左或右子树，若leftChild为true，删除左子树，否则删除右子树
	// 若p==null，将抛出空对象异常
	public void removeChild(Node<T> p, boolean leftChild) {
		if (leftChild)
			p.left = null;
		else
			p.right = null;
	}

	public void removeAll() // 删除二叉树的所有结点
	{
		this.root = null;
	}

	/**
	 * 返回二叉树的叶子结点数
	 */
	public int countLeaf() {
		return countLeaf(root);
	}

	private int countLeaf(Node<T> p) // 返回以p结点为根的子树的叶子结点个数
	{
		if (p == null)
			return 0;
		if (p.left == null && p.right == null)
			return 1;
		return countLeaf(p.left) + countLeaf(p.right);
	}

	// 复制以p根的子二叉树，返回新建子二叉树的根结点
	private Node<T> copy(Node<T> p) {
		if (p == null)
			return null;
		Node<T> q = new Node<T>(p.data);
		q.left = copy(p.left); // 复制左子树，递归调用
		q.right = copy(p.right); // 复制右子树，递归调用
		return q; // 返回建立子树的根结点
	}

}
